package mao.leetcode.others;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//????? 调试静态方法，需要在main函数里面打断点，否则会出错。
public class Solution_2 {
    List<Integer> list = new ArrayList<>();
    int maxDepth;
    int count;
    public static void main(String[] args) {

    }
     //leecode 94题
    //增加一个标签，表示已经展开过了还是没有展开过
    public List<Integer> inorderTraversal_3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null ) return list;
        Stack<ColoredTreeNode> s = new Stack<>();
        s.push(new ColoredTreeNode(true,root));
        while ( !s.isEmpty()){
            ColoredTreeNode n = s.pop();
            if (n.node == null) continue;
            if (n.folded){
                s.push(new ColoredTreeNode(true,n.node.right));
                n.folded=false;
                s.push(n);
                s.push(new ColoredTreeNode(true,n.node.left));
            }else list.add(n.node.val);
        }
        return list;
  }
    public class ColoredTreeNode{
        boolean folded = true;
        TreeNode node;
        public ColoredTreeNode(boolean folded, TreeNode node) {
            this.folded = folded;
            this.node = node;
        }
    }

    //莫里斯遍历，使用到了线索二叉树结构
    public List<Integer> inorderTraversal_2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null){
            if (cur.left == null){
                list.add(cur.val);
                cur=cur.right;  //只可能由于此处导致  cur = null;
            }else {
                TreeNode pre = cur.left;
                while (pre.right != null) pre=pre.right; //找到前驱节点
                pre.right = cur;
                TreeNode temp = cur;
                cur = cur.left;
                temp.left = null;
            }
        }
        return list;
    }

    //中序遍历的迭代写法，尝试改成前和后。
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); //需要处理的
        TreeNode cur = root;  //正在处理的
        while (cur != null || !stack.isEmpty()){
            while (cur != null){  //递归左侧，由于一直查找到 cur == null 所以右侧节点也可以被处理。
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur == null)  continue;
            list.add(cur.val); //递归中间
            cur= cur.right;    //处理右侧
        }
        return list;
    }
//    public List<Integer> inorderTraversal(TreeNode root) {
//        if (root == null) return list;
//        inorderTraversal(root.left);
//        list.add(root.val);
//        inorderTraversal(root.left);
//        return list;
//    }

  public int maxDepth(TreeNode root) {
          maxDepth_helper(root);
          return maxDepth;
    }
    public void maxDepth_helper(TreeNode root) {
        if (root == null)
            maxDepth = Math.max(maxDepth,count);
        else {
            count++;
            maxDepth_helper(root.left);
            maxDepth_helper(root.right);
            count--;
        }
    }
//    public int maxDepth(TreeNode root) {
//        if (root == null) return 0;
//        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
//    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric_helper(root.left,root.right);
    }
    public boolean isSymmetric_helper(TreeNode node1,TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 != null && node2 != null){
            if (node1.val == node2.val) return isSymmetric_helper(node1.left,node2.right) && isSymmetric_helper(node1.right,node2.left);
            else return false;
        }else return false;
    }


    //中序遍历在比较思路错误，应该提前搞清楚。
//    public boolean isSymmetric(TreeNode root) {
//        isSymmetric_helper(root);
//        for (int i = 0; i < list.size()/2; i++) {
//            if (list.get(i) != list.get(list.size()-i)) return false;
//        }
//        return true;
//    }
//    public void isSymmetric_helper(TreeNode root) {
//        if (root != null) {
//            isSymmetric_helper(root.left);
//            list.add(root.val);
//            isSymmetric_helper(root.right);
//        }
//    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p != null && q != null){
            if (p.val == q.val) return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
            else return false;
        }else return false;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
  }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index_merge = m+n-1,index_1 = m-1,index_2 = n-1;
        while (index_2>=0){
            if (index_1 >= 0 && nums1[index_1] > nums2[index_2]){
                nums1[index_merge] = nums1[index_1];
                index_1--;
                index_merge--;
            }else {
                nums1[index_merge] = nums2[index_2];
                index_2--;
                index_merge--;
            }
        }
     }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode tail = head,find = head.next;
        while ( find != null){
            if (find.val > tail.val){
                tail.next = find;
                tail = tail.next;
            }
            find = find.next;
        }
        tail.next = null;
        return head;
   }

    public class ListNode {
      int val;
       ListNode next;
      ListNode(int x) { val = x; }
  }



    public int climbStairs(int n) {
        if (n<3) return n;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n ; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public static int mySqrt_1(int x) {
        if (x == 0 || x==1) return x;
        double pre=0,cur=1;  //float 计算精度不够
        while (Math.abs(pre-cur)>1e-6){
            pre=cur;
           cur=(pre+x/pre)/2;
        }
        return (int)cur;
    }

    public static int mySqrt(int x) {
        if (x == 0 || x==1) return x;
        int left = 0 , right = x/2 , mid;
        while (left <= right){
            mid = left + (right -left)/2;
            long mut = (long) mid*mid; //int*int= int 要防止溢出
            if (x == mut) return mid;
            else if (x > mut) left = mid+1;
            else right = mid-1;
        }
        return right;
    }

    public String addBinary(String a, String b) {
        int ca = 0;
        int sum = 0;
        StringBuilder builder = new StringBuilder();
        for (int i = a.length()-1,j = b.length();i >= 0 || j >= 0;i--,j--){
            sum = ca;
            sum+= i >=0 ? a.charAt(i)-'0':0;
            sum+= j >=0 ? b.charAt(j)-'0':0;
            builder.append((char)( sum%2+'0'));
            ca=sum / 2;
        }
        builder.append(ca == 1? '1':"");
        return builder.reverse().toString();
    }

//    public String addBinary(String a, String b) {
//                int index = 0;
//                int flag = 0;
//                int chara,charb,sum;
//                StringBuilder builder = new StringBuilder();
//            while (index < a.length() && index < b.length()){
//                      chara = a.charAt(a.length()-1-index)-'0';
//                     charb = b.charAt(b.length()-1-index)-'0';
//                     sum = chara+charb+flag;
//                    builder.append((char)(sum%2+'0'));
//                    flag = sum/2;
//            index ++;
//        }
//        while (index < a.length()){
//              chara = a.charAt(a.length()-1-index)-'0';
//             sum = chara+flag;
//            builder.append((char)(sum%2+'0'));
//            flag = sum/2;
//            index ++ ;
//        }
//        while (index < b.length()){
//              charb = b.charAt(b.length()-1-index)-'0';
//             sum = charb+flag;
//            builder.append((char)(sum%2+'0'));
//            flag = sum/2;
//            index ++;
//        }
//        if (flag != 0) builder.append('1');
//        return builder.reverse().toString();
//    }

    public int[] plusOne(int[] digits) {
        int i = 0;
        for ( i = digits.length-1; i >=0 ; i++) {
            digits[i]++;
            if (digits[i] < 10) return digits;
            else digits[i] = 0;
        }

            int[] ans = new int[digits.length+1];
            ans[0] = 1;
            System.arraycopy(digits,0,ans,1,digits.length);
            return ans;
   }

    public static int lengthOfLastWord(String s) {
        if (s.trim().equals("")) return 0;
        int end,start;
        end=s.length()-1;
        while (end>=0 && s.charAt(end) == ' ') end --;
        start = end;
        while (start>=0 && s.charAt(start) != ' ' ) start--;
        return end-start;
    }
//    public static int lengthOfLastWord(String s) {
//        if (s.trim().equals("")) return 0;
//        //       if (s.charAt(s.length()-1) == ' ') return 0;
//        String[] s1 = s.split(" ");
//        for (int i = s1.length - 1; i >= 0; i--) {
//            if (!s1[i].trim().equals("")) return s1[i].length();
//        }
//        return 0;
//    }
}
